#include <string.h>
#include <vector>
#include "headfiles.h"

using namespace std;

bool isRepeatLetter(const char *str, 
                    size_t i,
                    bool *flag) {
    size_t j;
    for (j = 0; j < i; j++) {
        if (flag[j] == false && str[j] == str[i]) {
            return true;
        }
    }

    return false;
}

bool strPermutationRecur(const char *str, 
                         size_t size, 
                         bool *flag,
                         char *permu_str, 
                         size_t loc) {
    if (str == NULL) {
        cout << "String pointer is NULL!" << endl;
        return false;
    }

    if (loc == size) {
        permu_str[loc] = '\0';
        cout << permu_str << endl;
        return true;
    }

    size_t i;
    for (i = 0; i < size; i++) {
        if (flag[i] == false) {
            if (isRepeatLetter(str, i, flag)) {
                continue;
            }

            bool *sub_flag = (bool *)malloc(sizeof(bool) * size);
            memcpy(sub_flag, flag, sizeof(bool) * size);
            permu_str[loc] = str[i];
            sub_flag[i] = true;
            strPermutationRecur(str, size, sub_flag, permu_str, loc + 1);
            free(sub_flag);
        }
    }
}

bool stringPermutation(const char *str, size_t str_size) {
    char *permu_str = (char *)malloc(sizeof(char) * (str_size + 1));
    bool *flag = (bool *)malloc(sizeof(bool) * str_size);
    size_t i;
    size_t loc = 0;
    for (i = 0; i < str_size; i++) {
        memset(flag, 0, sizeof(bool) * str_size);
        if (isRepeatLetter(str, i, flag)) {
            continue;
        }
        permu_str[loc] = str[i];
        flag[i] = true;
        strPermutationRecur(str, str_size, flag, permu_str, loc + 1);
    }

    free(permu_str);
    free(flag);

    return true;
}

